import java.util.ArrayList;
import java.util.List;
// https://leetcode.cn/problems/combinations/description/
public class Combine {
    class Solution {
        List<List<Integer>> res = new ArrayList<>();
        public List<List<Integer>> combine(int n, int k) {

            backtracking(new ArrayList<>(),1,n , k);
            return res;


        }

        private void backtracking(List<Integer> path , int start, int end , int k)
        {
            if(path.size() == k)
            {
                res.add(new ArrayList<>(path));
                return;
            }
            for(int i = start; i <= end - (k - path.size()) +1 ; i++)
            {
                path.add(i);
                backtracking(path,i + 1, end, k);
                path.remove(path.size()-1);
            }

        }
    }
}
